class Solution
{
public:
    vector<int> platesBetweenCandles(string s, vector<vector<int>> &queries)
    {
        int n = s.size();
        vector<int> candlePrefixSum(n + 1);
        set<int> candleIndex;
        candlePrefixSum[0] = 0;
        for (int i = 0; i < n; ++i)
        {
            if (s[i] == '|')
            {
                candlePrefixSum[i + 1] = candlePrefixSum[i] + 1;
                candleIndex.insert(i);
            }
            else
            {
                candlePrefixSum[i + 1] = candlePrefixSum[i];
            }
        }

        vector<int> result;
        for (auto &query : queries)
        {
            int subSize = query[1] - query[0] + 1;
            int candleCount = candlePrefixSum[query[1] + 1] - candlePrefixSum[query[0]];
            if (candleCount < 2)
            {
                result.push_back(0);
            }
            else
            {
                int leftCandlePos = *candleIndex.lower_bound(query[0]);
                int rightCandlePos = *--candleIndex.upper_bound(query[1]);
                result.push_back(rightCandlePos - leftCandlePos + 1 - candleCount);
            }
        }
        return result;
    }
};